package util;

import org.junit.Test;

import java.util.HashMap;

/**
 * @author he peng
 * @create 2018/4/12 10:24
 * @see
 */
public class HashMapTest {

    @Test
    public void defaultConstructor() throws Exception {
        // DEFAULT_LOAD_FACTOR = 0.75f
        HashMap<Object, Object> map = new HashMap<>();
    }

    @Test
    public void tableSizeForJdk8() throws Exception {
        int cap = 10;
        int n = cap - 1;
        // n |= n >>> 1 , 先计算 f = n >>> 1 , 再计算 n | f
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        System.out.println(n);
        n = (n < 0) ? 1 : (n >= 1 << 30) ? 1 << 30 : n + 1;
        System.out.println("n = " + n);
        // 计算 HashMap 的初始化容量大小
    }

    @Test
    public void hash() throws Exception {
        Object key = "1ss";
        int h;
        int hash = (h = key.hashCode()) ^ (h >>> 16);
        System.out.println(hash);
    }

    @Test
    public void bucketIndex() throws Exception {
        Object key = 43354364334324L;
        System.out.println(key.hashCode());
        int h;
        int hash = (h = key.hashCode()) ^ (h >>> 16);
        System.out.println("hash % n = " + (hash % 4));
        System.out.println("4 - 1 ==> " + ((4 - 1) & hash));
        System.out.println("8 - 1 ==> " + ((8 - 1) & hash));
        System.out.println("16 - 1 ==> " + ((16 - 1) & hash));
        // (n - 1) & hash 计算得到的值会根据 n 的变化而变化 ,
        // 在 resize 的时候会进行 rehash
    }


    @Test
    public void put() throws Exception {

        // 在构造函数中指定的 initialCapacity 值并不是固定的初始大小 , 构造函数中会使用这个
        // 值去计算一个 threshold （当 size 达到 threshold 后就会进行一次 resize） ,
        // 在首次 resize 时会真正的去创建存储空间 , 首次 resize 时会使用 threshold 的值
        // 去作为初始空间的大小

        // 建议在初始化 Map 对象的时候指定一个初始化大小 ， 否则第一次 resize 的时候
        // 就会用默认的 16 作为初始大小，很有可能造成内存空间的浪费
        HashMap<Object, Object> map = new HashMap<>(4);
        Object obj = map.put("k", "v");

        // 计算 key 的 hash 值 ,  (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
    }

    @Test
    public void putValue() throws Exception {
//        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
//        if ((tab = table) == null || (n = tab.length) == 0)
//            n = (tab = resize()).length;
        // TODO (n - 1) & hash 计算出 bucket 的位置
//        if ((p = tab[i = (n - 1) & hash]) == null)
              // TODO 如果计算出来的 bucket 位置上还还没有节点 ， 就创建一个新节点放置在该 bucket 位置上
//            tab[i] = newNode(hash, key, value, null);
//        else {
//            HashMap.Node<K,V> e; K k;
              // TODO 判断当前存入的 key 于该 bucket 位置上已经存在的节点 key 是否相同 （hash  ，key == ， key equals ）
//            if (p.hash == hash &&
//                    ((k = p.key) == key || (key != null && key.equals(k))))
//                e = p;
//            else if (p instanceof HashMap.TreeNode)
//                e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//            else {
                  // TODO 在 bucket 位置上的链表后面添加新的节点
//                for (int binCount = 0; ; ++binCount) {
//                    if ((e = p.next) == null) {
//                        p.next = newNode(hash, key, value, null);
//                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//                            treeifyBin(tab, hash);
//                        break;
//                    }
//                    if (e.hash == hash &&
//                            ((k = e.key) == key || (key != null && key.equals(k))))
//                        break;
//                    p = e;
//                }
//            }
//            if (e != null) { // existing mapping for key
//                V oldValue = e.value;
//                if (!onlyIfAbsent || oldValue == null)
//                    e.value = value;
//                afterNodeAccess(e);
//                return oldValue;
//            }
//        }

          // TODO 当 HashMap 每次使用 bucket 上一个新的位置时 ，才有可能去 resize
//        ++modCount;
//        if (++size > threshold)
//            resize();
//        afterNodeInsertion(evict);
//        return null;
    }

    @Test
    public void get() throws Exception {
        HashMap<Object, Object> map = new HashMap<>(4);
        map.put("k", "v");
        map.put("k1", "v1");
        map.put("k2", "v2");

        System.out.println("value = " + map.get("k1"));
        // 计算出 key 在 bucket 中的位置 ， 依次比较该位置链表上的元素 ，
        // 直到发生 key 碰撞 ， 或者是达到链表的尾部
    }



    @Test
    public void resizeJdk8() throws Exception {
//        if (oldCap > 0) {
//            if (oldCap >= MAXIMUM_CAPACITY) {
//                threshold = Integer.MAX_VALUE;
//                return oldTab;
//            }
        // TODO 如果容量还没有达到最大值 ， 同时达到了默认初始容量 ， 会增长 1 倍
        // TODO 初始容量为 1 << 4 = 16
//            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
//                    oldCap >= DEFAULT_INITIAL_CAPACITY)
//                newThr = oldThr << 1; // double threshold
//        }
        // TODO 如果容量 <= 0 , threshold > 0 , 会以 threshold 的大小作为新的容量大小
//        else if (oldThr > 0) // initial capacity was placed in threshold
//            newCap = oldThr;
        // TODO threshold ， 容量都不具备 ， 使用默认初始容量大小
//        else {               // zero initial threshold signifies using defaults
//            newCap = DEFAULT_INITIAL_CAPACITY;
//            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
//        }

        HashMap<Object, Object> map = new HashMap<>(4);
        map.put("k", "v");
        map.put("k1", "v1");
        map.put("k2", "v2");
        map.put("k3", "v3");
        map.put("k4", "v4");
        map.put("k5", "v5");
        map.put("k6", "v6");
    }

    @Test
    public void node() throws Exception {
        // TODO map 中key的哈希值
//        final int hash;

        // TODO map 中key值
//        final K key;

        // TODO map 中的value值
//        V value;

        // TODO 下一个 Node 的引用
//        HashMap.Node<K,V> next;
//
//        Node(int hash, K key, V value, Node<K,V> next) {
//            this.hash = hash;
//            this.key = key;
//            this.value = value;
//            this.next = next;
//        }
    }

}